/**
 * 链表中的内部节点类
 */
class Node {
  /**
   * @param {any} data 当前节点数据
   */
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

/**
 * 链表结构类
 */
class LinkedList {
  /**
   * @public head 链表的头部
   * @public length 链表的长度
   */
  constructor() {
    this.head = null;
    this.length = 0;
  }

  /**
   * 位置判断: 数字是否为正整数，是否超出链表长度
   *
   * 返回true为不通过
   *
   * @param {Number} position 插入或删除的位置
   * @return {Boolean}
   */
  isInteger(position) {
    if (!Number.isInteger(position)) {
      return true;
    }
    if (position < 0) {
      return true;
    }
    if (position > this.length) {
      return true;
    }
    return false;
  }

  /**
   * 向尾部添加一个元素
   * @param {*} element
   */
  push(element) {
    // 创建新节点
    let newNode = new Node(element);

    // 判断添加的是否为第一个节点
    if (this.head === null) {
      this.head = newNode;
    } else {
      let current = this.head;

      // 找到最后一个节点
      while (current.next) {
        current = current.next;
      }

      // 把最后节点的next指向新的节点
      current.next = newNode;
    }

    // 节点长度加1
    this.length++;
  }

  /**
   * 向列表的特定位置插入一个元素
   * @param {Number} position 插入的位置
   * @param {*} element 插入的元素
   * @return {Boolean} true: 插入成功，false: 插入失败
   */
  insert(position, element) {
    if (this.isInteger(position)) {
      return false;
    }

    // 创建新的节点
    let newNode = new Node(element);

    // 如果插入的位置是第一个
    if (position == 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 插入位置的前一个节点
      const previous = this.getElementAt(position - 1);
      const current = previous.next;
      // newNode的左边
      previous.next = newNode;
      // newNode的右边
      newNode.next = current;
    }

    this.length++;

    return true;
  }

  /**
   * 获取对应位置的元素,找到返回元素，否则返回undefined
   * @param {Number} position 元素索引
   * @return {Element|undefined}
   */
  getElementAt(position) {
    // 最多只能获取到length - 1 的位置
    if (this.isInteger(position)) {
      return undefined;
    }

    let index = 0;
    let current = this.head;
    while (index++ < position) {
      current = current.next;
    }
    return current;
  }

  /**
   * 返回元素在链表中的索引。如果找不到返回-1
   * @param {*} element 元素
   * @return {Number}
   */
  indexOf(element) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (JSON.stringify(current.data) == JSON.stringify(element)) {
        return index;
      }
      current = current.next;
      index += 1;
    }
    return -1;
  }

  /**
   * 修改某个位置的元素
   * @param {Number} position 修改的位置
   * @param {*} newElement 新元素
   * @return {Boolean}
   */
  update(position, newElement) {
    if (this.isInteger(position)) {
      return false;
    }

    let current = this.head;
    let index = 0;
    while (index++ < position) {
      current = current.next;
    }

    current.data = newElement;

    return true;
  }

  /**
   * 移除一个特定位置的元素
   * @param {Number} position 移除的位置
   * @return {*} 成功: 返回删除的元素，失败: 返回null
   */
  removeAt(position) {
    if (this.isInteger(position)) {
      return undefined;
    }

    let current = this.head;

    if (position == 0) {
      current = this.head.next;
    } else {
      // 前面的节点
      let previous = this.getElementAt(position - 1);
      // 前面节点, 跳过current
      current = previous.next;
      previous.next = current.next;
    }

    this.length--;

    return current.data;
  }

  /**
   * 从链表中移除一个元素
   * @param {*} element 移除的元素
   * @return {*} 成功: 返回删除的元素，失败: 返回undefined
   */
  remove(element) {
    let position = this.indexOf(element);
    if (position) {
      return this.removeAt(position);
    } else {
      return undefined;
    }
  }

  /**
   * 如果链表中不包含任何元素，返回true
   * @return {Boolean}
   */
  isEmpty() {
    return this.length == 0;
  }

  /**
   * 返回链表包含的元素个数
   * @return {Number}
   */
  size() {
    return this.length;
  }

  /**
   * 将链表中所有的元素，以字符串形式输出
   * @returns {String}
   */
  toString() {
    let current = this.head;
    let listString = "";

    while (current) {
      listString += current.data + " ";
      current = current.next;
    }

    return listString;
  }
}

/********************双向链表************************/
class DoublyNode extends Node {
  constructor(data) {
    super(data);
    this.prev = null;
  }
}
class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    this.tail = null; //指向最后一个元素
  }
  /**
   * @param {Number} index - 插入点
   * @param {any} data -插入元素
   * @returns {Boolean} 插入是否成功
   */
  insert(index, data) {
    if (this.isInteger(index)) {
      return false;
    }
    const node = new DoublyNode(data);
    // 1. 向首部插入
    if (index === 0) {
      // 如果链表为空
      if (this.length === 0) {
        this.head = node;
        this.tail = node;
      } else {
        // 链表不为空时:
        // 1.1 插入点位置元素prev， 指向新节点
        this.head.prev = node;
        // 1.2 新节点的next，指向插入点元素
        node.next = this.head;
        // 1.3 修改首部指针指向
        this.head = node;
      }
    } else if (index === this.length) {
      // 2. 向尾部插入
      // 2.1 插入点元素(this.tail)next，指向新节点
      this.tail.next = node;
      // 2.2 新元素prev，指向插入点元素
      node.prev = this.tail;
      // 2.3 修改尾部指针指向
      this.tail = node;
    } else {
      // 3. 向中间插入
      // 3.1 找到插入点
      let current = this.head;
      let position = 0;
      while (position++ < index) {
        current = current.next;
      }
      // 3.2 将新节点的next指向插入点
      node.next = current;
      // 3.2 将新节点的prev指向插入点的prev
      node.prev = current.prev;
      // 3.3 将插入点的父节点的next指向新节点
      current.prev.next = node;
      // 3.3 将插入点的prev指向node
      // 必须最后才修改插入点，否则无法获取current.prev
      current.prev = node;
    }
    this.length++;
    return true;
  }
  /**
   * 向尾部插入
   * @param {any} data -插入元素
   */
  push(data) {
    const node = new DoublyNode(data);
    // 1. 插入时是第一个
    if (this.length === 0) {
      this.tail = node;
      this.head = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
  }
  /**
   * 获取链表字符串形式
   * @returns {String}
   */
  toString() {
    let current = this.head;
    let resultString = "";
    while (current) {
      resultString +=
        typeof current.data === "string"
          ? current.data
          : JSON.stringify(current.data);
      current = current.next;
    }
    return resultString;
  }
  /**
   *  根据指定索引获取链表项
   *  @param {Number} position -链表索引
   *  @returns {Node|undefined} -链表项 {data: '', ....}
   */
  getElementAt(position) {
    if (this.isInteger(position)) {
      return undefined;
    }

    let current = null;
    let index = 0;

    // 从头开始遍历
    if (this.length / 2 > position) {
      current = this.head;
      while (index++ < position) {
        current = current.next;
      }
    } else {
      // 从尾开始遍历
      current = this.tail;
      index = this.length - 1;
      while (index-- > position) {
        current = current.prev;
      }
    }
    return current;
  }
  /**
   * 修改某个位置的元素
   * @param {Number} position 修改的位置
   * @param {*} newElement 新元素
   * @return {Boolean}
   */
  update(position, newElement) {
    if (this.isInteger(position)) {
      return false;
    }

    let current = this.getElementAt(position);

    if (current) {
      current.data = newElement;
    } else {
      return false;
    }

    return true;
  }
  /**
   * 移除一个特定位置的元素
   * @param {Number} position 移除的位置
   * @return {Node|Boolean} 成功: 返回删除的元素，失败: 返回false
   */
  removeAt(position) {
    if (this.isInteger(position)) {
      return false;
    }

    let current = this.head;

    // 1. 当链表只有一个节点
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      // 2. 当删除第一个节点
      if (position === 0) {
        // 2.1 把第二个节点变成第一个节点
        this.head.next.prev = null;
        // 2.2 改变首部指针
        this.head = this.head.next;
      } else if (position === this.length - 1) {
        // 存储改变之前，用于返回
        current = this.tail;
        // 3 删除最后一个节点
        // 3.1 倒数第二个节点变成最后一个节点
        this.tail.prev.next = null;
        // 3.2 改变尾部指针
        this.tail = this.tail.prev;
      } else {
        // 4. 删除的节点
        let findNode = this.getElementAt(position);
        current = findNode;
        findNode.prev.next = findNode.next;
        findNode.next.prev = findNode.prev;
      }
    }

    this.length--;

    return current.data;
  }
}

/******************测试************************/

const linkedList = new LinkedList();
console.log(linkedList.size()); // 0
console.log(linkedList.isEmpty()); // true
linkedList.push(1);
linkedList.push(3);
linkedList.push(2);
linkedList.push(5);
console.log(linkedList.size()); // 4
let node = linkedList.getElementAt(2);
console.log(node);
console.log(linkedList.indexOf(5)); // 3
console.log(linkedList.indexOf(8)); // -1
console.log(linkedList.insert(1, 9)); // true
console.log(linkedList.toString()); // 1,9,3,2,5
console.log(linkedList.remove(2)); // 2
console.log(linkedList.toString()); // 1,9,3,5
console.log(linkedList.removeAt(2)); // 3
console.log(linkedList.toString()); // 1,9,5

/************************双链表************************/
const doublyList = new DoublyLinkedList();
doublyList.insert(0, "AAA");
doublyList.insert(1, "BBB");
doublyList.insert(1, "CCC");
doublyList.insert(1, "DDD");
console.log(doublyList.toString(), doublyList.size()); // AAA DDD CCC BBB
doublyList.update(3, "DDD2");
console.log(doublyList.toString());
doublyList.removeAt(3);
console.log(doublyList.toString());
